# 周登举的Python
# 开发时间: 2021/5/19   19:51
import numpy as np
import random
import matplotlib.pyplot as plt
import math
import copy
import pandas


class Sol:
    def __init__(self):
        self.nodes_seq = None    #节点的序列
        self.value = None      #解的适应度值
        self.routes = None     #子路径的集合


#产生初始解节点序列
def GenInintalSol():
    nodes_seq=list(range(1,21))
    random.shuffle(nodes_seq)
    return nodes_seq


#计算两个坐标之间的距离
def CalDistance(current_node,next_node):   #这俩参数是1到20的整数型
    distance = math.sqrt((x_coord[next_node] - x_coord[current_node]) ** 2 + (y_coord[next_node] - y_coord[current_node]) ** 2)  # 用于计算任意两点间距离的公式
    return distance


#切分子路径
'''
输入是一个解
输出是这个解的切分好的子路径，子路径的负载，子路径的行驶距离，这个解的值
'''
def CalRoute(nodes_seq):
    routes=[]    #用于存储各个子路径的集合
    vehicle_node=[]   #子路径中点的集合
    sub_route_distance_set=[]
    current_load=0
    current_distance=0
    current_node=0   #起点
    for i in range(1,len(nodes_seq)+1):
       next_node=nodes_seq[i-1]    #当前节点   是确确实实坐标的编号 从1到20   x_coord[next_node]就是next_node的横坐标
       next_node_demand=W[next_node-1]   #需求量的索引从0开始，减掉1才是该点在需求列表中对应的需求量
       distance = CalDistance(current_node, next_node)
       distance_last_zero=CalDistance(next_node,0)
       if current_distance+distance+distance_last_zero <= LMax and current_load+next_node_demand<=WMax:     #应该是让点先加进去，然后在判断，如果不满足就不加进去
           current_distance +=distance
           current_load +=next_node_demand
           vehicle_node.append(next_node)
           current_node = next_node  #这个点变成当前点了
       else:
           vehicle_node.append(0)       #在最后的位置加上0点构成闭合回路
           vehicle_node.insert(0,0)     #在第一个位置加上0起点
           routes.append(vehicle_node)
           distance=CalDistance(current_node,0)
           current_distance+=distance    #判断条件里没有加上最后一个点到0点的距离
           sub_route_distance_set.append(current_distance)
           current_node=0
           next_node=nodes_seq[i-1]
           vehicle_node = [next_node]    #当前子路径里的点
           current_distance=CalDistance(current_node,next_node)   #当前距离
           current_load=W[nodes_seq[i-1]-1]    #当前载重
           current_node=nodes_seq[i-1]
    vehicle_node.append(0)
    vehicle_node.insert(0, 0)
    routes.append(vehicle_node)
    distance = CalDistance(current_node, 0)
    current_distance += distance
    sub_route_distance_set.append(current_distance)
    current_sol_value=0
    for i in range(len(sub_route_distance_set)):
        current_sol_value  = current_sol_value + sub_route_distance_set[i]
    return nodes_seq,current_sol_value,routes


#实现领域变换
def Change(nodes_seq):
    current_list=copy.deepcopy(nodes_seq)      #一定要用copy,不用就会出问题
    random_number=random.random()
    list_tempt = random.sample(list(range(20)), 2)  # 产生的是列表的下标
    if random_number>=0 and random_number<0.3:
        current_list[list_tempt[0]], current_list[list_tempt[1]] = nodes_seq[list_tempt[1]], nodes_seq[list_tempt[0]]
    elif random_number>=0.3 and random_number<0.8:
        if list_tempt[1]>list_tempt[0]:
            bit_one=list_tempt[0]
            bit_two=list_tempt[1]
        else:
            bit_one=list_tempt[1]
            bit_two=list_tempt[0]
        sub_list_one= nodes_seq[0:bit_one]
        sub_list_two= nodes_seq[bit_one:bit_two + 1]     #两个变化位之间的元素
        sub_list_three= nodes_seq[bit_two + 1:]
        little_list=copy.deepcopy(sub_list_two)                      #一定要用copy,不用就会出问题
        little_list.reverse()   #使两变化位之间反转
        current_list=sub_list_one+little_list+sub_list_three
    else:
        if list_tempt[1] > list_tempt[0]:
            bit_one = list_tempt[0]
            bit_two = list_tempt[1]
        else:
            bit_one = list_tempt[1]
            bit_two = list_tempt[0]
        sub_list_one= nodes_seq[0:bit_one + 1]
        sub_list_one.append(nodes_seq[bit_two])
        current_list= sub_list_one + nodes_seq[bit_one + 1:bit_two] + nodes_seq[bit_two + 1:]
    return current_list


#绘图部分
def plot(history_best_sol_value_set):
    plt.rcParams['font.sans-serif'] = ['SimHei']  # show chinese
    plt.rcParams['axes.unicode_minus'] = False  # Show minus sign
    plt.plot(np.arange(1,len(history_best_sol_value_set)+1), history_best_sol_value_set)
    plt.xlabel('迭代次数')
    plt.ylabel('当前最好解')
    plt.grid()
    plt.xlim(1, len(history_best_sol_value_set) + 1)
    plt.show()

#主函数
def Main(x_coord,y_coord,W,WMax,LMax,TMax,TMin,Alpha,iter):  #iter是内循环次数
    T = TMax
    sol= Sol()
    sol.nodes_seq = GenInintalSol()    #初始解的序列
    sol.nodes_seq,sol.value,sol.routes = CalRoute(sol.nodes_seq)   #初始解
    best_sol=copy.deepcopy(sol)       #最好解
    history_best_sol_value_set=[]      #历史最好解值的集合
    history_best_sol_value_set.append(sol.value)
    while T >= TMin:
        for i in range(iter):
            new_sol=Sol()
            new_sol.nodes_seq=Change(sol.nodes_seq)
            new_sol.nodes_seq, new_sol.value, new_sol.routes=CalRoute(new_sol.nodes_seq)
            deta_f=new_sol.value-sol.value
            if deta_f < 0 or math.exp(-deta_f / T) > random.random():
                sol = copy.deepcopy(new_sol)
            if sol.value < best_sol.value:
                best_sol = copy.deepcopy(sol)
        history_best_sol_value_set.append(best_sol.value)
        T=Alpha*T
    plot( history_best_sol_value_set)
    best_sol.nodes_seq, best_sol.value, best_sol.routes=CalRoute(best_sol.nodes_seq)
    return  best_sol.nodes_seq, best_sol.value, best_sol.routes

if __name__ == '__main__':
    x_coord=[14.5,12.8,18.4,15.4,18.9,15.5,3.9,10.6,8.6,12.5,13.8,6.7,14.8,1.8,17.1,7.4,0.2,11.9,13.2,6.4,9.6]  #横坐标
    y_coord=[13.0,8.5,3.4,16.6,15.2,11.6,10.6,7.6,8.4,2.1,5.2,16.9,2.6,8.7,11.0,1.0,2.8,19.8,15.1,5.6,14.8]   #纵坐标
    W=[0.1,0.4,1.2,1.5,0.8,1.3,1.7,0.6,1.2,0.4,0.9,1.3,1.3,1.9,1.7,1.1,1.5,1.6,1.7,1.5]   #各客户点需求量
    Alpha=0.96  #降温系数
    TMax=100   #初始温度
    TMin=0.01    #终止温度
    WMax=8    #车辆最大载重量
    LMax=50   #车辆最大行驶距离
    iter=100  #内循环次数
    best_sol=Sol()
    best_sol.nodes_seq, best_sol.value, best_sol.routes=Main(x_coord,y_coord,W,WMax,LMax,TMax,TMin,Alpha,iter)
    print("最好解的所有子路径依次是",best_sol.routes)
    print("最好解的节点序列是",best_sol.nodes_seq)
    print("最好解的总行驶距离是",best_sol.value)